如何通过因果涌现找到复杂网络的合适尺度？

导语

复杂网络在不同尺度上会表现出不同的特性，并反映出不同的信息量。比如脑神经网络的微观放电能在宏观尺度上涌现自我意识。那么，如何找到能反映网络最佳信息量的尺度呢？“因果涌现”概念的提出者 Erik Hoel 在 arXiv 预印本上的一篇文章介绍了寻找网络合适尺度的方法。这篇文章发现谱分析的方法优于贪婪算法和梯度下降法，能够更好地识别网络的中观和宏观尺度，并证明了这些尺度在信息传输方面比其底层微观尺度具有显著的优势，包括确定性的增加、简并性的减少、网络中随机游走的熵率较低、全局网络效率的增加以及各种中心性度量比微观尺度具有更高的值等特性。

集智俱乐部组织的因果涌现读书会第二季正在进行中，基于因果涌现理论、机器学习重整化技术、自指动力学等前沿理论，研讨复杂系统的涌现谜题。读书会由北京师范大学教授张江和加州大学圣地亚哥分校助理教授尤亦庄等人发起，每周日晚19:00举办。读书会后续将对本篇论文进行更加详细的在线解读，欢迎感兴趣的朋友参与，详情见文末。

研究领域：因果涌现，复杂网络，多尺度，信息论

刘志航 | 作者

邓一雪 | 编辑

论文题目：

Finding the right scale of a network: Efficient identification of causal  emergence through spectral clustering

论文来源：

https://arxiv.org/abs/1908.07565#

从还原论的视角上看，微观的的模型往往比宏观尺度模型更能反映系统的特征，因为微观尺度包含了系统的所有细节。然而，Erik P. Hoel 等人在论文《量化因果涌现表明：宏观可以战胜微观》[1]发现，当粗粒化处理后的宏观机制相比于底层微观机制具有更高的有效信息，而这种现象被称为因果涌现（causal emergence）。

这种现象在我们生活中随处可见。例如动物群体在逃避捕食者时，微观尺度呈现的是随机游走的状态，而宏观尺度上看会涌现出一种确定性的规避模式。这种确定性就为我们理解一个复杂系统的提供了“有效信息”（effective information, EI），这种有效信息可以理解为一种对因果联系的度量，即对系统运行机制进行的描述可以捕捉系统中可能出现的过去和未来状态的程度。而因果涌现就是从微观尺度迁移到宏观尺度分析时获得的有效信息的增益。

所以我们可以发现，在复杂系统的不同层级和不同尺度中，存在不同的因果关系，甚至有可能存在跨尺度的因果联系。而为了更准确的理解复杂系统，我们就需要找到哪个尺度上的因果联系才能为我们理解复杂体现提供最多的“有效信息”。

1. 从微观到宏观：复杂网络的因果涌现

复杂网络可以用来表征广泛现实的系统。虽然网络分析通常是在网络的完整、微观尺度上进行的，但这篇论文的作者最近的研究表明[2]，信息量更大的网络系统可以被识别和明确地建模。如图1 所示，一个网络 G，可以重塑为一个新的网络 G_M，其中网络 G 的子图被分组为单个的宏节点（macro-nodes）。

这些宏观节点以重现原始网络动态的方式总结了子图的行为。因此，更高的尺度的网络就像原始系统的一致但降维的模型。随着节点和边的增加，网络的规模和复杂度会呈指数级增加，因此这种降维对于理解网络的特性是有必要的。但是，这种从微观到宏观尺度的转变是否真的能保留甚至增益原有网络的有效信息呢？

图1. 从微观尺度的原始网络 G （上），到宏观尺度的新网络 G_M  （下）

为了解决这个问题，做出从信息论出发，提出了一个测量不同网络尺度有效信息的指标——EI。每个网络节点 v_i 都有权重向量 ，它表示该节点与邻居节点的输出权重，如果权重为0，则表明该节点与邻居节点没有连边。 每个节点的输出权重总和为 1，  因此这个权重可以理解为位于该节点的随机游走者在下一个时间步转移到其邻居节点的概率（如图 2 所示）。因此，作为因果联系衡量指标的有效信息（EI），可以量化随机游走者在节点之间转换的确定性程度，以及这种确定性是如何分布的。 所以 EI 可以用以下公式计算得出：

是网络中平均权重向量的香农熵，它反映了网络权重的分布情况。每个节点权重向量的平均熵，反映了节点输出的不确定性。网络中权重分布的熵形成了网络关系中唯一信息量的上限，减去由于这些关系的不确定性而丢失的信息，我们就能得到网络的确定性信息（有效信息）EI 。EI 可以简单地理解为网络上随机游走者的结构属性及其行为的确定性。

图2. 小世界网络的随机游走 | 笔者自绘

从以上的衡量标准我们可以知道，复杂网络的因果涌现，就是新的宏观尺度上网络有效信息高于原始微观尺度网络的有效信息的情况。宏观尺度上的网络是有宏节点组成的网络，每个宏节点都是微节点组成的子图，作者将任何带有宏节点的网络称为宏尺度，其中没有宏节点的网络称为微尺度。

值得注意的是，宏尺度通常具有同一性的，因为它们将产生与底层微尺度相同或近似相同的动态。这可以通过比较每个尺度上随机游走者的动态来评估，看看宏观尺度在多大程度上再现了微观尺度的动态。而寻找描述复杂系统最合适尺度的任务就可以转化为寻找产生 EI 增益的宏节点的迭代过程，也即寻找使网络产生因果涌现的过程。

2. 衡量不同网格尺度因果涌现的三种方法

这种搜索合适网络尺度的迭代过程会随着系统的大小呈指数级增长，这会带来很高的计算成本。在这篇文章中，作者比较和评估了三种不同的方法，即贪婪算法、梯度下降法以及网络谱分析方法。

贪婪算法评估一个节点被划分到周围子图后 EI 的变化，如果这个划分使得 EI 增加，算法会存储这一变化，并改变节点的队列，加入新的不属于该子图的邻居节点，从而扩大搜索范围。每对节点都由算法进行迭代检查，直到每个节点都经过测试。

梯度下降法是一种解决各种优化问题的有效方法，是机器学习中普遍存在的一种方法。可以将 EI 作为一个集合划分函数，并用一个矩阵 M 来代替集合划分区。具体来说，该方法通过将微尺度邻接矩阵乘以 M 得到候选宏尺度网络，然后计算宏尺度网络的 EI 作为 M 和网络邻接矩阵的函数，计算 EI 相对于 M 的梯度，并使用标准梯度下降算法利用这个梯度最大化 EI。该方法的缺点是M的收敛依赖于随机初始化，可能会在同一个网络上多次运行不同的结果，性能还取决于梯度下降中使用的学习率，以及允许的最大迭代次数。

谱分析一直是网络划分算法中比较理想的以及具有良好线性代数理论基础的方法。由于网络的连通性和代数结构之间存在很强的关系，因此作者认为谱分析用于确定尺度的有效性是高于以上两种方法的。网络的邻接矩阵可以理解为是网络上随机游走的转移概率矩阵。谱算分析算法是计算 W^out 的特征分解，W^out 的非零特征值和对应的特征向量包含了丰富的网络拓扑结构信息。

然后，将网络中的每个节点与该节点的每个特征向量的项组成的向量联系起来，通过取这些向量的余弦相似度来计算网络中所有节点对的距离，最后使用谱聚类算法应用到这个距离矩阵上，以获得网络节点上的聚类，将其输出解释为从微观尺度到新的宏观尺度的映射。聚类的效果取决于于聚类中使用的距离阈值，而最优值取决于网络的拓扑结构，且难以选择先验。因此，作者在一系列值上检查EI增益，以找到最佳聚类。利用线性代数的工具，作者在邻接矩阵的基本属性和网络的 EI 之间建立了联系。

图3. 因果涌现计算方法的比较。α 值是通过添加连边的进程在调用每个函数期间使用的系统和用户 CPU 时间来计算的。（A）贪婪算法和梯度下降法都难以检测 α  =1.5 附近的中尺度，而谱分析保持相对不变。（B）运行时间与网络大小。贪婪算法在小实例上比梯度下降算法更有效，而梯度下降算法在更大的网络上更有效，谱分析的性能优于两者。（C）不同算法发现 α 值不同的无标度网络的因果涌现。（D）与网络规模相比，检测到的因果涌现，谱分析略优于贪婪算法，梯度下降落后于两者。

图 3 对比了三种方法性能，作者分析了150 个节点的优先连接网络在不同 α 值的运行时间。当α = 1 时是无标度网络，而 α 接近 0 则产生长路径的树，当α > 2 导致放射式模型。值得注意到的是，极端微观尺度（最小到没有因果涌现）和极端宏观尺度（高水平的因果涌现）不需要太多的计算资源。

中尺度结构通常是网络中计算上最难识别的尺度。然而，谱分析在很大程度上避免了这一问题，它具有最强大的算法性能，即使在大型网络中也能找到信息量大且复杂的更高尺度（图3B）。虽然所有算法都能识别因果涌现，但谱分析和贪婪算法似乎都表现得更好，能找到等价的复杂网络因果涌现尺度。

3. 复杂网络的宏观尺度性质

为了探索如何找到有效信息更大的网络，作者模拟了优先连接规则下增长的网络，通过向网络中添加一个新节点和它的 m 条新边来增加网络规模，通过操纵 α 以可控的方式跨越一系列不同的网络连接。同时，优先连接的网络可以跨越因果涌现的范围，从因果退化（causal reduction，即当 α < 1 时通过降维无法获得 EI ）到所有节点被分组为单个宏节点（α > 3时）。

图4.  网络的宏尺度示例。（A）50个节点（m = 1）的优先连接网络随着 α 的增加而呈现。我们的谱分析用于识别宏节点。通过算法分组成宏节点的节点用颜色编码。（B）m = 3 的优先连接网络，这意味着随着每一步增加更多的边，网络更加密集。信息宏节点也出现在 α 的更高层次上。

通过谱分析，图4A 显示了 50 个节点网络的宏结点涌现。如果 α < 1，对应于亚线性优先连接区域，在该区域网络无法在更高尺度上出现有效信息。一旦优先连接是超线性的，因果涌现就变得重要。那么，不同尺度下的网络的属性存在什么差异呢？

我们从有效信息（EI）的定义可知，有效信息越高意味着网络有更高的确定性或更小的简并性。确定性是网络中平均权重向量的香农熵，而所谓简并性则是网络权值分布不均匀程度的一个度量。从图5B 可以看出，因果涌现的宏观网络的不确定性减小，而图5C 则显示了在宏观尺度下简并性的减小。这意味着随机游走者在网络的宏观尺度上面临更少的不确定性。在图5D 中，展示了随机游走者的熵率（每一时间步产生的不确定度大小）如何在因果涌现的宏观尺度下比在微观尺度下低得多。

图5. 不同尺度下的优先连接网络的属性。（A）对于不同的α 值的因果涌现量。（B）更高的尺度上确定性的增加。（C）更高尺度上简并性的减小。（D）随机游走在微观和宏观尺度上对网络平稳分布的熵率。（E）网络的效率提高。（F）中介性中心性。（G）中心性。（H）网络中节点的可交流性序列熵。（I）网络的平均度降低。（J）节点度方差随着 α 的增加而增加。（K）随着α的增加，度关联性降低。（L）核维数与网络的简并性有关。它从概率的角度量化了从一个时间步到下一个时间步收敛到相同分布的随机游走的分布空间。

在因果关系涌现的情况下，宏观上的全局网络效率也可能更高（图5E）。这表明宏节点通信或交互比它们的底层微观尺度更有效，因为平均路径长度要低得多。同时，在因果涌现后，网络节点的平均中心性显著增加（图5F）。由于中介中心性可以被解释为网络中节点对信息传输的控制程度的量化，这表明宏观尺度比微观尺度对网络信息传输动态的控制程度更高。随着 α 的增加，宏节点的平均特征向量中心性开始增加（图5G）。

网络特性的这些广泛而显著的变化表明了网络中宏观尺度的有效识别是多么重要，以及为什么重要。值得注意的是，尽管宏观尺度和微观尺度的这些属性发生了变化，但它们在随机游走动力学方面仍然是一致的，这表明网络属性通常依赖于尺度。

4. 寻找更高的网络尺度并不是社区检测

寻找有效信息的更高的网络尺度是一个非常类似于网络社区发现的过程，这两者有什么区别呢？

首先，寻找宏节点类似于识别节点的社区，但社区检测通常侧重于组内连通性大于组外连通性的子图。相比之下，宏观节点表示子图，它们在网络中具有可行的行为汇总统计，具体来说，它们寻求保持随机游走者的行为，同时减少其行为的不确定性。因为重要的是它们的形成是随机行走行为被保留，宏节点可以超过一个连接范围。此外，在找到合适的子图分区后，宏节点是通过将这些子图转换为单独的节点来重铸网络本身。

其次，识别网络中的因果涌现有很多好处，不仅可以减少网络的维度，也可以改善网络从结构到信息的各种属性。与原始的微观尺度相比，偶然涌现的宏观尺度可以表现出：不确定性的降低、简并性的降低、平稳分布下随机漫游走者的熵率的降低、全局网络效率的提高、平均中间中心性的提高以及核维的降低。因此，网络科学家如果想了解网络的功能和结构，就必须明确地建立更高尺度的模型。

参考文献

[1] Hoel, E. P., Albantakis, L., & Tononi, G. (2013). Quantifying causal emergence shows that macro can beat micro. Proceedings of the National Academy of Sciences, 110(49), 19790-19795.

[2] Klein, B., & Hoel, E. (2020). The emergence of informative higher scales in complex networks. Complexity.

因果涌现读书会第二季招募中

跨尺度、跨层次的涌现是复杂系统研究的关键问题，生命起源和意识起源这两座仰之弥高的大山是其代表。而因果涌现理论、机器学习重整化技术、自指动力学等近年来新兴的理论与工具，有望破解复杂系统的涌现规律。同时，新兴的因果表示学习、量子因果等领域也将为因果涌现研究注入新鲜血液。

由北京师范大学教授、集智俱乐部创始人张江和加州大学圣地亚哥分校助理教授尤亦庄等人发起的「因果涌现」系列读书会第二季，将组织对本话题感兴趣的朋友，深入研读相关文献，激发科研灵感。本读书会自2022年5月22日开始，每周日晚19:00举办，预计持续7-8周。欢迎感兴趣的朋友报名参与。

本季读书会详情与报名方式请参考：

推荐阅读

点击“阅读原文”，报名读书会